// -*- coding: utf-8 -*- 
/**
 * Project: AlgorithmsLearn
 * Creator: yanking
 * Create time: 2022-02-24 14:47
 * IDE: IntelliJ IDEA
 * Introduction:
 */
package com.leetCode.DeleteColumnsToMakeSorted;

import java.util.ArrayList;

public class DeleteColumnsToMakeSorted {
    public int minDeletionSize(String[] strs) {
        // 删除字符串数组中的字符使得字符串数组中的字符串是按照字典序进行排序
        // 字符串中的字符长度相等
        // 1 找出字符串数组中不符合字典序排列的字符
        // 2 可以比较两个字符串是否按照字典序进行排序
        return findChar(strs);

    }

    // Get The Unalphabetically words
    private int findChar(String[] strs) {
        int len2 = strs[0].length();
        ArrayList<Integer> deleteIndex = new ArrayList<>();// 删除索引序列
        for (int i = 0; i < len2; i++) {
            if (isNoAlphabetic(strs, i)) {
                // 当前位置字典序错误
                deleteIndex.add(i);
                break;
            }
        }
        return deleteIndex.size();

    }

    private boolean isNoAlphabetic(String[] strs, int i) {
        // To Predicate A String Array In A Specific Location If Is Alphabetic
        // 字典序可以是升序排序也可以是降序排序
        int len = strs.length;
        int pre, cur = 0;
        for (int j = 1; j < len; j++) {
            pre = cur;
            cur = strs[j - 1].charAt(i) - strs[j].charAt(i);
            if (cur < 0 && pre > 0 || cur > 0 && pre < 0) { // 相邻三个字符字典序不一样
                return true;
            }
        }
        return false;
    }


}
